1. Field of the Invention
The present invention generally relates to the art of microelectronic integrated circuits, and more specifically to a physical design automation system and process for designing integrated circuit chips using "chessboard" and "sieve" optimization.
2. Description of the Related Art
Microelectronic integrated circuits consist of a large number of electronic components that are fabricated by layering several different materials on a silicon base or wafer. The design of an integrated circuit transforms a circuit description into a geometric description which is known as a layout. A layout consists of a set of planar geometric shapes in several layers.
The layout is then checked to ensure that it meets all of the design requirements. The result is a set of design files in a particular unambiguous representation known as an intermediate form that describes the layout. The design files are then converted into pattern generator files that are used to produce patterns called masks by an optical or electron beam pattern generator.
During fabrication, these masks are used to pattern a silicon wafer using a sequence of photolithographic steps. The component formation requires very exacting details about geometric patterns and separation between them. The process of converting the specifications of an electrical circuit into a layout is called the physical design. It is an extremely tedious and an error-prone process because of the tight tolerance requirements and the minuteness of the individual components.
Due to the large number of components and the exacting details required by the fabrication process, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use Computer Aided Design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process has increased the level of integration, reduced turn around time and enhanced chip performance.
The objective of physical design is to determine an optimal arrangement of devices in a plane or in a three dimensional space, and an efficient interconnection or routing scheme between the devices to obtain the desired functionality. Since space on a wafer is very expensive real estate, algorithms must use the space very efficiently to lower costs and improve yield. The arrangement of individual cells in an integrated circuit chip is known as a cell placement.
Each microelectronic circuit device or cell includes a plurality of pins or terminals, each of which is connected to pins of other cells by a respective electrical interconnect wire network or net. A goal of the optimization process is to determine a cell placement such that all of the required interconnects can be made, and the total wirelength and interconnect congestion are minimized.
Prior art methods for achieving this goal comprise generating one or more initial placements, modifying the placements using optimization methodologies including genetic algorithms such as simulated evolution, force directed placement or simulated annealing, and comparing the resulting placements using a cost criteria.
A major drawback of these prior art methodologies as implemented using a conventional digital computer is their sequential nature. Since integrated circuits commonly include hundreds of thousands of cells that must be placed and routed, computer run times are unacceptably long for practical commercial applications.
Attempts have been made to overcome the limitations of prior art algorithms by dividing a chip into a number of regions, and simultaneously optimizing the placements inside the regions using respective parallel processors. Each processor has its own copy of the chip, and works only in the region(s) to which it is assigned. There is another, master copy of the chip which is updated periodically to reflect the changes in the individual regions.
A major problem inherent in this approach is that, during one period between two consecutive updates of the master copy, a processor working in a given region does not see the changes being made in the other regions by the other processors, and bases all placement change decisions on the cell positions in the previous master copy.
The drawbacks of the prior art are illustrated in FIGS. 3a and 3b. A net N interconnects cells C1 and C2 which are located in regions R1 and R2 of an integrated circuit chip. A goal of the placement optimization is to minimize the total wirelength of the placement.
The processor working in the region R1 sees the cell C2 in the previous master copy of the chip, and moves the cell C1 toward the cell C2 in the direction of an arrow D1 to reduce the length of the net N. Similarly, the processor working in the region R2 sees the cell C1 in the previous master copy of the chip, and moves the cell C2 toward the cell C1 in the direction of an arrow D2 to reduce the length of the net N.
The result is illustrated in FIG. 3b. The positions of the cells C1 and C2 have been essentially reversed with relation to each other, and the length of the net N is substantially unchanged.
Another limitation of the prior art is that with optimization being performed locally within a plurality of regions, a cell is not able to be moved from one region to another even though the optimal position for the cell is in a region far remote from the region in which it is initially located.